//
//  Problem22.swift
//  LeetCode - 22 - 括号生成
//
//  Created by 武侠 on 2020/7/6.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit
/*
 [22 括号生成]
 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 示例：
 输入：n = 3
 输出：[
        "((()))",
        "(()())",
        "(())()",
        "()(())",
        "()()()"
      ]
 */
class Problem22: NSObject {
    func solution() {
        
//        print("n = 2", generateParenthesis(2))
//        print("n = 3", generateParenthesis(3))
        print("n = 4", generateParenthesis(4))
        
        // 动态规划:
//        print("n = 3", getStr2(3))
//        print("n = 4", getStr2(4))
    }
    
    func generateParenthesis(_ n: Int) -> [String] {
        if n <= 0 {
            return []
        } else if n == 1 {
            return ["()"]
        }
        
        let ar1 = self.getStr1("((", n - 2, n, [])
        let ar2 = self.getStr1("()", n - 1, n - 1, [])
        print(ar1)
        print(ar2)
        return ar1 + ar2
    }
    
    // 深度优先遍历 + 剪枝 + 自己实现的
    func getStr(_ str: String, _ left: Int, _ right: Int, _ array:[String]) -> [String] {
        if left < 0 {
            return []
        } else if right < 0 {
            return []
        }
        var arrayList = array
        if left <= right, left > 0, right > 0 {
            let s1 = self.getStr(str + "(", left - 1, right, array)
            arrayList.append(contentsOf: s1)
            if left != right {
                let s2 = self.getStr(str + ")", left, right - 1, array)
                arrayList.append(contentsOf: s2)
            }
        } else if left > 0 {
            let s1 = self.getStr(str + "(", left - 1, right, array)
            arrayList.append(contentsOf: s1)
        } else if right > 0 {
            let s2 = self.getStr(str + ")", left, right - 1, array)
            arrayList.append(contentsOf: s2)
        } else {
            arrayList.append(str)
        }
        return arrayList
    }
    
    // 深度优先遍历 + 剪枝 + 优化
    func getStr1(_ str: String, _ left: Int, _ right: Int, _ array:[String]) -> [String] {
        print(str, left, right, array)
        var arrayList = array
        if left == 0, right == 0 {
            arrayList.append(str)
            return arrayList
        }
        
        if  left > right {  // 剪枝
            return []
        }
        
        if left > 0 {
            let s1 = self.getStr1(str + "(", left - 1, right, array)
            arrayList.append(contentsOf: s1)
        }
        
        if right > 0 {
            let s2 = self.getStr1(str + ")", left, right - 1, array)
            arrayList.append(contentsOf: s2)
        }
        return arrayList
    }
    
    // 动态规划, 原理: p + q = n - 1      p和q 都是子数组
    // n = ( p ) + q
    
    // ["()"]
    // ["(())", "()()"]
    // 3 = ( 0 ) + 2    ()(()) ()()()
    // 3 = ( 1 ) + 1    (())() ()(())
    // 3 = ( 2 ) + 0    ((())) (()())
    // ["((()))", "(()())", "(())()", "()(())", "()()()"]
    func getStr2(_ n: Int) -> [String] {
        if n <= 0 {
            return []
        } else if n == 1 {
            return ["()"]
        }
        
        var lists:[[String]] = [[""], ["()"]]
        for i in 2...n {
            var l: [String] = []
            for j in 0..<i {
                let list1 = lists[j]
                let list2 = lists[i - j - 1]
                
                var list3:[String] = []
                
                for item1 in list1 {
                    for item2 in list2 {
                        list3.append("(" + item1 + ")" + item2)
                    }
                }
                print(i, j, i - j - 1, list3)
                l.append(contentsOf: list3)
            }
            lists.append(l)
        }
        print(lists)
        return lists[n]
    }
    

}
